\section{Applications}\label{sec:apps}

While the previous sections focused on performing the fundamental primitive of random walks efficiently, in this section we show that these techniques, while of independent interest, actually directly help to improve on specific applications as well. We also highlight the fact that the following application results are specifically strong and novel for the dynamic setting, and therefore crucially rely on our round complexity guarantees and strong bounds in this dynamic distributed network framework. Hence previous results on random walks in static networks did not yield the following performance improvements in well-studied problems.

\subsection{Information Dissemination (or $k$-Gossip) Problem}
In this section, we present a fully distributed algorithm for {\em $k$-gossip} problem in regular stationary evolving graphs. The algorithm runs in two phases. In the first phase we send some $f$ copies of each token $t$ to random nodes. We use algorithm {\sc Many-Random-Walk} (cf. algorithm~\ref{alg:many-random-walk}) to do this. In second phase we simply broadcast each token $t$ from the random places to reach all the nodes. The pseudo code is given in Algorithm \ref{alg:token-dissemination} in the Appendix. It is shown that if every node having a token $t$ broadcasts it for $O(n\log n/f)$ rounds, then with high probability all the nodes will receive the token $t$. 

\begin{algorithm}
\caption{\sc K-Information-Dissemination($\mathcal{G}$, $k$)}
\label{alg:token-dissemination}
\textbf{Input:} An evolving graphs $\mathcal{G}: G_1, G_2, \ldots$ and $k$ token in some nodes.\\
\textbf{Output:} To disseminate $k$ tokens to all the nodes.\\

\textbf{Phase 1: (Send $f$ copies of each token to random places)}
\begin{algorithmic}[1]
%\FOR{each token $t$}
\STATE  Every node holding token $t$, send $f$ copies of each token to random nodes using algorithm {\sc Many-Random-Walk}.
%\ENDFOR

\end{algorithmic}


\textbf{Phase 2: (Broadcast each token for $O(n\log n/f)$ rounds)}
\begin{algorithmic}[1]
\FOR{each token $t$}
\STATE  For the next $2 n\log n/f$ rounds, let all the nodes has token $t$ broadcast the token.
%\STATE When algorithm {\sc Single-Random-walk} terminates, the sampled destination outputs ID of the source $s_j$. 
\ENDFOR
\end{algorithmic}

\end{algorithm}


\noindent \textbf{Analysis.} Using the time complexity of our $k$ Random  Walks algorithm, we   analyze the round complexity of  our algorithm (cf. Algorithm \ref{alg:token-dissemination}), and show that it solves the $k$-gossip problem in $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3})$ rounds. 
To make sure that the algorithm terminates in $O(nk)$ rounds, 
we run this algorithm in parallel with the trivial algorithm (which just broadcast each of the $k$ tokens sequentially; clearly this will take $O(nk)$ rounds in total) and stops when one of the two algorithms stop.  Thus the claimed bound in Theorem   \ref{thm:token-bound}  holds.

%\begin{lemma}\label{lem:node-counting}
%Let $G_1, G_2, \ldots$ be a sequence of $d$-regular stationary evolving graphs. Let a token $t$ be broadcasted from a particular node $v$ for $O(R)$ rounds. Then there is at least $O(R)$ nodes receives the token $t$. In other words, there is at least $O(R)$ nodes from which $v$ is reachable if broadcast so many rounds.    
%\end{lemma}


%\begin{theorem}\label{thm:token-bound}
%The algorithm~(cf. Algorithm~\ref{alg:token-dissemination} in Appendix) solves {\em $k$-gossip} problem with high probability in $\tilde{O}(\min\{n^{1/3}k^{2/3}(\tau \Phi)^{1/3}, nk\})$ rounds. 
%\end{theorem}
The mixing time $\tau$ of a regular dynamic graph is at $O(n^2)$ (follows from Theorem~\ref{thm:mixtime} and Corollary~\ref{cor:second-eigen-bound} in the Appendix). Putting this in Theorem  \ref{thm:token-bound}, yields a better  bound for $k$-gossip problem in a regular dynamic graph. 
%\begin{corollary}\label{cor:token-bound-tauless}
%The algorithm~(cf. algorithm~\ref{alg:token-dissemination} in Appendix) solves {\em $k$-gossip} problem with high probability in $\tilde{O}(\min\{n k^{2/3} \Phi^{1/3}, nk\})$ rounds. 
%\end{corollary}

%**Note: I think a more careful analysis of lemma~\ref{lem:node-counting} improves the round complexity by a factor of $d$ since we consider $d$-regular graphs. 

\subsection{Decentralized Estimation of Mixing Time}
We present an approach to estimate the mixing time of a regular connected non-bipartite stationary evolving graphs $\mathcal{G} = G_1, G_2, \ldots$. Suppose all graphs $G_t$ has the same mixing time, say $\tau_{mix}$. We want to estimate the dynamic mixing time $\tau$ of the dynamic graph $\mathcal{G}$. We discussed in Section \ref{sec:model} that this $\tau$ is essentially same as $\tau_{mix}$. While the definition of $\tau$ itself is consistent, estimating this value becomes significantly harder in the dynamic context. The intuitive approach of estimating distributions continuously and then adapting a distribute-closeness test works well for static graphs, but each of these steps becomes far more involved and expensive when the network itself changes and evolves continuously. Therefore we need careful analysis and new ideas in obtaining the following results. Due to lack of space we placed this section in the Appendix (Section \ref{application mixing time}).

\iffalse
Among the two techniques we present, due to lack of space we placed the second approach in Section \ref{application mixing time} in Appendix. We present the first approach below. We also introduce some notation and definitions in Appendix (Section \ref{application mixing time}) before formalizing our approach and theorem.
%We present two different approach here to estimate mixing time of a regular evolving graphs.
 
\noindent\textbf{First approach.}\\
The idea behind this technique is to observe returns of simple random walks to the starting nodes on dynamic networks. This is an idea that was completely unexplored in the past work on random walks in distributed networks. For simplicity we assume that the dynamic network is node transitive so that mixing time of a simple random walk starting from any vertex is same (this can be eliminated). Initially we start with some random walks, say $c\log n$ ($c$ is small constant) from each vertex in parallel, gives total $c n\log n$ walks and after mixing time it is expected that total $c\log n$ walks would return to their starting vertex. We show this with high probability in the following lemma. 

\begin{lemma}\label{lem:total-return}
Let $c\log n$ many random walks starts parallely from every vertex of the network. Then after reaching mixing time ($\tau$) the total number of walks return to its corresponding starting vertex is $c\log n$ with high probability.  
\end{lemma}

Our algorithm starts with length $\ell = \log n$ and runs $c\log n$ random walks of length $\ell$ parallely form each vertex. Then count the number of returns to each corresponding starting vertex of all random walks. If the total count is closer to $c \log n$ then output the value of $\ell$ as mixing time of the network. Otherwise, double the value of $\ell$ and retry. We use the algorithm {\sc Many-Random-Walks} to perform $c\log n$ walks from each vertex. Counting the total number of returns of random walks can be done by flooding in at most $O(\Phi)$ rounds where $\Phi$ is dynamic diameter of the network. The round complexity of this algorithm is $\tilde{O}(n^{1/2}\sqrt{\tau \Phi})$ stated in the Theorem~\ref{thm:mixing estimate bound} in Section~\ref{sec:results}.  

%\begin{theorem}\label{thm:mixing estimate bound}
%The above algorithm estimate the dynamic mixing time $\tau$ of a node transitive graph in $\tilde{O}(n^{1/2}\sqrt{\tau \Phi})$ rounds, with high probability. 
%\end{theorem}

Our estimation of mixing time $\tau$ of the node transitive graph would allow us to estimate several related quantities. Given a mixing time $\tau$, we can approximate the spectral gap ($1-\lambda_2$) and the conductance ($\Psi$) due to the known relations that $\frac{1}{1-\lambda_2}\leq \tau \leq \frac{\log n}{1-\lambda_2}$ and $\Theta(1-\lambda_2)\leq \Psi \leq \Theta(\sqrt{1-\lambda_2})$ as shown in~\cite{JS89}. 
  
%\begin{theorem}
%Given a node transitive evolving graphs with dynamic diameter $D$, a node $x$ can find, in $\tilde O(n^{1/2} + n^{1/4} \sqrt{D\tau(\epsilon)})$ rounds, a time $\tilde \tau_{mix}$ where $\epsilon = \frac{1}{6912e\sqrt{n} \log n}$. (Shall write it carefully)
%\end{theorem} 
\fi


